package leetcode.D500.T450;

import util.TreeNode;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2021-06-25 1:41:02 星期五
 */

class Solution {
    // 一刷
    /*private int successor(TreeNode root) {
        TreeNode suc = root.right;
        while(suc.left != null) {
            suc = suc.left;
        }
        return suc.val;
    }

    private int predecessor(TreeNode root) {
        TreeNode pred = root.left;
        while(pred.right != null) {
            pred = pred.right;
        }
        return pred.val;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) {
            return null;
        }
        if(key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if(root.left == null && root.right == null) {
                root = null;
            } else if(root.right != null) {
                root.val = successor(root);
                root.right = deleteNode(root.right, root.val);
            } else {
                root.val = predecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }*/

    // 二刷
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null && root.right == null)
                root = null;
            else if (root.right != null) {
                TreeNode next = root.right;
                while (next.left != null)
                    next = next.left;
                root.val = next.val;
                root.right = deleteNode(root.right, next.val);
            } else {
                TreeNode prev = root.left;
                while (prev.right != null)
                    prev = prev.right;
                root.val = prev.val;
                root.left = deleteNode(root.left, prev.val);
            }
        }
        return root;
    }
}